Research Seminar in Combinatorics and Graph Theory (238902)
Winter semester 2011/12
last updated: 22.10.2011
Announced as 238901 (because the course 238902 is still awaiting
senate approval).
Structural Graph Theory and Algorithmic Meta-theorems
NEW (tba):
List of topics for seminar talks.
NEW (tba):
Slides of given lectures
For those graduate students who have already taken 238901 before,
but on another topic, arrangements will be found
to get credit again.
Lecturer: Prof. J.A. Makowsky and participants
NEW TIME: Sunday, 12:30-14:30
New Place: Taub 4
Prerequisites:
Some elementary graph theory,
Computability.
Format:
Two hours frontal presentations.
Requirements:
Edited version of frontal presentation or
final project.
Outline
One of the great achievements in graph theory is the
emergence of a structural theory initiated by the work
of
N. Robertson and P. Seymour and their students and collaborators.
The prototype of a structural theorem concerns the characterization of
minor closed graph classes and the notion of tree-width of a graph.
More recently, other notions of width emerged, such as clique-width and
rank-width, for which there are also structural theorems.
The basic theory is well covered in the book
Graph Theory by R. Diestel.
The structural theory of graphs also led to
algorithmic meta-theorems, theorems of the form
Every problem of the from xxxxx has certain algorithmic properties
Here xxxxx can be a definability condition like
contsraint satisfaction problems, classes of graphs of fixed width
definable in some formalism, etc.
A survey of such theorems can befound in my recently edited
book,
available on line,
in particular the paper by
http://www.cs.technion.ac.il/~janos/COURSES/238902-11/
The first meeting of the seminar is on
Sunday, 30 October, 12:30, Taub 4
Feel free to contact me before that if you have any questions.